#include <iostream>
int count = 0;
//冒泡排序
void BubbleSort(int *a,int size)
{
    for(int i = 0; i < size-1;i++)
    {   
        count++;
        int flag = 0;
        for(int j = 0;j < size-i-1;j++)
        {
            if(a[j]>a[j+1])
            {   
                flag = 1;
                int temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp;
            }
        }

        if(flag == 0)
        {
            break;
        }
    }
    printf("count : %d\n",count);
}

//插入排序
void InsertSort(int*a,int size)
{
    for(int i = 1;i < size;i++)
    {
        int j = i;
        int temp = a[i];
        for(;j > 0;j--)
        {
            if(temp < a[j-1])
            {
                a[j] = a[j-1];
            }
            else
            {
                break;
            }
        }
        a[j] = temp;
    }  
}

//选择排序
void SelectSort(int*a,int size)
{
    for(int i = 0;i < size-1;i++)
    {
        int min = i;
        for(int j = i+1;j < size;j++)
        {
            if(a[j] < a[min])
            {
                min = j;
                
            }
        }
        int temp = a[i];
        a[i] = a[min];
        a[min] = temp;
    }
}

//双指针算法
void SelectSort2(int*a,int size)
{
    int left = 0;
    int right = size-1;
    for(;left<right;left++,right--)
    {
        int min = left;
        int max = right;
        for(int i = left;i <= right;i++)
        {
            if(a[i] < a[min])
            min = i;
            if(a[i] > a[max])
            max = i;
        }
    std::swap(a[left],a[min]);
    if(max == left)
    {
        max = min;
    }
    std::swap(a[right],a[max]);
    }
}

//快速排序
void QuickSort(int *a,int start,int end)
{   
    //终止条件
    if(start >= end)
        return;
    
    int left  = start;
    int right = end;
    int temp = a[left];
    while(left < right)
    {
        while(left < right &&a[right] > temp)
        {
            right--;
        }
        if(left < right)
            a[left++]  = a[right];
        while(left < right&&a[left] < temp)
            left++;
        if(left < right)
            a[right--] = a[left];
    }
    a[left] =  temp;

    QuickSort(a,start,left-1);
    QuickSort(a,right+1,end);

}

//递归思想

int main()
{   
    int a[] = {2,5,1,9,3,7};
    //冒泡排序
    QuickSort(a,0,sizeof(a)/sizeof(a[0])-1);

    for(int i = 0; i < sizeof(a)/sizeof(a[0]);i++)
    {
        std::cout<<a[i]<<" ";
    }

    std::cout<<std::endl;
    return 0;
}